#include<iostream>
#include <vector>
using namespace std;

int FindRight(int *arr, int len, int root)
{
    for (int i = len - 1; i >= 0; i--)
    {
        if (arr[i] > root)
        {
            return i;
        }
    }
    return -1;
}

int FindLeft(int *arr, int len, int root)
{
    for (int i = len - 1; i >= 0; i--)
    {
        if (arr[i] < root)
        {
            return i;
        }
    }
    return -1;
}

bool Verify(int *arr, int len)
{
    int root = arr[len - 1];
    int right_index = FindRight(arr, len - 1, root);
    int left_index = FindLeft(arr, len - 1, root);
    if (left_index == -1 && right_index == -1)
        return true;
    if (left_index > right_index && right_index != -1)
        return false;
    bool result = true;
    if (left_index != -1 && arr[left_index] > root)
        result = false;
    if (result)
    {
        if (right_index != -1 && arr[right_index] < root)
            result = false;
    }
    if (!result)
        return false;

    if (left_index != -1)
    {
        result = Verify(arr, left_index + 1); // 判断左子树
    }
    if (result && right_index != -1)
    {
        result = Verify(arr + left_index + 1, right_index - left_index); // 判断左子树
    }
    return result;
}

bool VerifySquenceOfBST(vector<int> sequence)
{
    if (sequence.size() <= 1)
        return true;
    return Verify(&sequence[0], sequence.size());
}

int main()
{
    vector<int> arr = {2,4,3};
    cout << VerifySquenceOfBST(arr) << endl;

    arr = {2};
    cout << VerifySquenceOfBST(arr) << endl;
    arr = {2,3,4};
    cout << VerifySquenceOfBST(arr) << endl;
    arr = {3,4,2};
    cout << VerifySquenceOfBST(arr) << endl;

    arr = {1,3, 2, 4, 2};
    cout << VerifySquenceOfBST(arr) << endl;
    
    return 0;
}